home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / m_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.1 KB  |  97 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  m_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_M_HEAP_H
  17. #define LEDA_M_HEAP_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // m_heap : monotonic heaps 
  21. //
  22. // a) the sequence of minimum keys (over time) is monotonic (non-decreasing)
  23. // b) the difference of minimum and maximum key is bounded by a constant M
  24. //
  25. // Implementation: cyclic array of lists
  26. //
  27. // Stefan Naeher  (1991)
  28. //------------------------------------------------------------------------------
  29.  
  30.  
  31. #include <LEDA/basic.h>
  32. #include <LEDA/list.h>
  33.  
  34.  
  35. typedef list_item m_heap_item;
  36.  
  37. class m_heap {
  38.  
  39.     int start;
  40.     int offset;
  41.     int M;
  42.     int count;
  43.     list<GenPtr> L;
  44.  
  45.     list_item*   T;
  46.  
  47. virtual void copy_inf(GenPtr&)  const {}
  48. virtual void clear_inf(GenPtr&) const {}
  49. virtual void print_inf(GenPtr x) const { cout << x; }
  50.  
  51. protected:
  52.  
  53. m_heap_item item(void* p) const { return (m_heap_item)p; }
  54.  
  55. public:
  56.  
  57. m_heap_item insert(GenPtr,GenPtr);
  58. m_heap_item find_min() const;
  59. m_heap_item first_item() const;
  60. m_heap_item next_item(m_heap_item) const;
  61.  
  62. GenPtr       del_min();
  63.  
  64. void change_key(m_heap_item,GenPtr);
  65. void decrease_key(m_heap_item it,GenPtr x) { change_key(it,x); }
  66. void change_inf(m_heap_item it, GenPtr x)  { copy_inf(x); L[it] = x; };
  67. void del_item(m_heap_item);
  68. void clear();
  69.  
  70. GenPtr inf(m_heap_item it) const { return L.inf(it); }
  71.  
  72. GenPtr key(m_heap_item) const
  73. { error_handler(1,"m_heap::key not implemented");
  74.   return 0; 
  75.  }
  76.  
  77. int    size()   const     { return count; }
  78. int    empty()  const     { return count==0; }
  79.  
  80. void   print() const;
  81.  
  82.  m_heap(int M=1024);         
  83.  m_heap(int,int) { error_handler(1,"illegal constuctor"); }
  84.  
  85. virtual ~m_heap() { delete T; }
  86.  
  87.  
  88. // still to do: copy operations
  89.  
  90.  m_heap& operator=(const m_heap&) { return *this; }
  91.  m_heap(const m_heap&) {}
  92.  
  93. };
  94.  
  95. #endif
  96.  
  97.